package policy

import "errors"

type tQuickSortPolicy struct {
	mLeftStack *tIntStack
	mRightStack *tIntStack
}

func NewQuickSortPolicy() ISortPolicy {
	return &tQuickSortPolicy{
		newIntStack(),newIntStack(),
	}
}

type tIntStack struct {
	tail *tIntNode
	size int
}

type tIntNode struct {
	Value int
	Prev *tIntNode
}

func newIntNode(value int) *tIntNode {
	return &tIntNode {
		value, nil,
	}
}

func newIntStack() *tIntStack {
	return &tIntStack{
		nil,
		0,
	}
}

func (self *tIntStack) Push(i int) {
	node := newIntNode(i)
	node.Prev = self.tail
	self.tail = node
	self.size++
}

func (self *tIntStack) Pop() (error,int) {
	if self.size > 0 {
		self.size--
		node := self.tail
		self.tail = self.tail.Prev
		return nil, node.Value

	} else {
		return errors.New("empty stack"), 0
	}
}

func (self *tIntStack) Size() int {
	return self.size
}

func (self *tQuickSortPolicy) Name() string {
	return "QuickSort"
}

func (self *tQuickSortPolicy) Sort(data []int) []int {
	self.qsort(data, 0, len(data) - 1)
	return data
}


func (self *tQuickSortPolicy) qsort(data []int, from int, to int)  {
	if to <= from {
		return
	}

	if to == from + 1 {
		if data[to] < data[from] {
			data[from], data[to] = data[to], data[from]
		}
		return
	}

	iPivot := (from + to) / 2
	vPivot := data[iPivot]

	left := 0
	right := 0
	for i := from; i <= to; i++ {
		if i == iPivot {
			continue
		}

		v := data[i]
		if v <= vPivot {
			self.mLeftStack.Push(v)
			left++
		} else {
			self.mRightStack.Push(v)
			right++
		}
	}

	// pop right stack
	p := to
	for i := right; i > 0; i-- {
		e,v := self.mRightStack.Pop()
		if e != nil {
			panic(e)
		}
		data[p] = v
		p--
	}

	// pop pivot
	data[p] = vPivot
	p--

	// pop left stack
	for i := left; i > 0; i-- {
		e,v := self.mLeftStack.Pop()
		if e != nil {
			panic(e)
		}
		data[p] = v
		p--
	}

	self.qsort(data, from, from + left - 1)
	self.qsort(data, to - right + 1, to)
}